/**
 * 判断单链表是否有环
 * 这里环的定义是：链表的最后一个节点，指向了这个链表的任何一个节点（不一定是头）
 * 
 * 使用快慢指针
 * 如果有环的话，那么快指针一定会追上慢指针，且在环内相遇
 * 如果没有环的话，一直循环，肯定会出现null
 */

#include"LinkedList.h"
LinkedList * haveLoop(LinkedList *head){
    LinkedList* fast =head;
    LinkedList * slow=head;
    while (fast!=nullptr&&fast->next!=nullptr)
    {
        slow=slow->next;
        fast=fast->next;
        if(fast==slow) break;//快慢相遇，就说明有环，可以退出了
    }
    //fast没有null就说明没有环，则返回null
    if(fast==nullptr||fast->next==nullptr){
        return nullptr;
    }
    //分别指向开始节点和相遇的节点
    LinkedList* p1=head,*p2=slow;
    while (p1!=p2)//为什么这样就能找到入口？答案中有推导
    /**
     * 链表头到环的入口节点的距离是 x
     * 入口节点到快慢指针相遇节点的距离是 y
     * 环的长度是 r
        在两指针相遇时，慢指针走的总路程为 x + y，快指针走的总路程为 2(x + y)。
        快指针比慢指针多走了一个完整的环，即 x + y + r = 2(x + y)，由此推导出 x = r - y。
        所以，当一个指针从链表头开始，另一个从相遇点开始以相同的速度移动时，它们会在环的入口相遇。
     */
    {
        p1=p1->next;
        p2=p2->next;
    }
    return p1;//返回入口点

}

/**
 * 时间复杂度为O(n)
 * 空间复杂度为O(1)
 */
